package main

//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
//
//
//
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
//
//
//
// 示例 1：
//
//
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：[["Q"]]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 9
//
//
//
// Related Topics 数组 回溯 👍 1219 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
var result [][]string

func solveNQueens(n int) [][]string {
	result = [][]string{}
	queens := make([]int, n)
	for i := 0; i < n; i++ {
		queens[i] = -1
	}
	columns, dia1, dia2 := make([]int, n), make([]int, 2*n), make([]int, 2*n+1)
	backTrack(queens, n, 0, columns, dia1, dia2)
	return result
}

func backTrack(queens []int, n, row int, columns, dia1, dia2 []int) {
	// 如果到了最后一行
	if n == row {
		dis := display(queens)
		result = append(result, dis)
		return
	}
	// 遍历每一列
	for i := 0; i < n; i++ {
		// 如果该列中已经有皇后了，则不能放这里
		if columns[i] == 1 {
			continue
		}
		// 如果正斜线中已经有皇后列，则不能放这里
		// row-i可以用于代表[row,i]所处的正斜线，-n<row-i<n
		if dia1[row-i+n] == 1 {
			continue
		}
		// row+i可以用于代表[row,i]所处的反斜线，-1<row+i<2n
		if dia2[row+i+1] == 1 {
			continue
		}
		columns[i], dia1[row-i+n], dia2[row+i+1] = 1, 1, 1
		// 第row行的皇后应该放在第i列
		queens[row] = i
		// 继续找下一行的皇后位置
		backTrack(queens, n, row+1, columns, dia1, dia2)
		// 回溯
		columns[i], dia1[row-i+n], dia2[row+i+1] = 0, 0, 0
		queens[row] = -1
	}
}

func display(queens []int) (ans []string) {
	for i := 0; i < len(queens); i++ {
		var a []rune
		for j := 0; j < len(queens); j++ {
			if j == queens[i] {
				a = append(a, 'Q')
			} else {
				a = append(a, '.')
			}
		}
		ans = append(ans, string(a))
	}
	return ans
}

//leetcode submit region end(Prohibit modification and deletion)
